home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 231_01 / turing.st < prev    next >
Encoding:
Text File  |  1987-06-15  |  3.8 KB  |  125 lines
  1. "
  2.     Turing machine simulator contributed by Jan Gray,
  3.         the University of Waterloo
  4. "
  5. Class Main
  6. [
  7.     main            | tm |
  8.         tm <- TuringMachine new initialize.
  9.         tm delta state: 0 input: $# nextState: 1 output: $L.
  10.         tm delta state: 1 input: $I nextState: 1 output: $i.
  11.         tm delta state: 1 input: $i nextState: 1 output: $L.
  12.         tm delta state: 1 input: $# nextState: 2 output: $R.
  13.         tm delta state: 2 input: $i nextState: 2 output: $R.
  14.         tm delta state: 2 input: $# nextState: 'halt' output: $#.
  15.         tm tape: 'IIIIII'.
  16.         tm delta print.
  17.         tm run
  18. ]
  19. Class TuringMachine
  20. |       tape            "Infinite tape"
  21.         state           "Current state, TM continues if state is a number"
  22.         delta           "A TransitionTable, which for each (state, input)
  23.                          gives (next state, output)"
  24.         tapeMoves       "A Dictionary which maps L and R into [tape left]
  25.                          and [tape right]"
  26. |
  27. [
  28.         initialize
  29.                 tapeMoves <- Dictionary new.
  30.                 tapeMoves at: $L put: [tape left].
  31.                 tapeMoves at: $R put: [tape right].
  32.                 delta <- TransitionTable new.
  33.                 self tape: ''.
  34.                 self state: 0
  35. |
  36.         tape: aString
  37.                 tape <- Tape new with: aString
  38. |
  39.         state: aState
  40.                 state <- aState
  41. |
  42.         delta
  43.                 ^ delta
  44. |
  45.         step
  46.                 | next |
  47.                 next <- delta atState: state input: tape read.
  48.                 state <- next state.
  49.                 (state isKindOf: Number)
  50.                         ifTrue: [(tapeMoves includesKey: next symbol)
  51.                                         ifTrue:  [(tapeMoves at: next symbol) value]
  52.                                         ifFalse: [tape write: next symbol]]
  53. |
  54.         run
  55.                 state <- 0.
  56.                 self print.
  57.                 [state isKindOf: Number] whileTrue: [self step print]
  58. |
  59.         printString
  60.                 ^ 'State ', state printString, ', Tape ', tape printString
  61. ]
  62. Class Pair    :Magnitude
  63. | state symbol |
  64. [
  65.         state: aState symbol: aSymbol
  66.                 state <- aState.
  67.                 symbol <- aSymbol
  68. |
  69.         state
  70.                 ^ state
  71. |
  72.         symbol
  73.                 ^ symbol
  74. |
  75.     < aPair
  76.         ^ state < aPair state or:
  77.             [state = aPair state and: [symbol < aPair symbol]]
  78. |
  79.         printString
  80.                 ^ state printString, '    ', symbol printString
  81. ]
  82. Class TransitionTable :Dictionary
  83. [
  84.         state: aState input: in nextState: nextState output: out
  85.                 self at: (Pair new state: aState symbol: in)
  86.                      put: (Pair new state: nextState symbol: out).
  87.         ^ nil
  88. |
  89.         atState: aState input: in
  90.                 ^ self at: (Pair new state: aState symbol: in)
  91.                        ifAbsent: [^ Pair new state: 'hung' symbol: nil].
  92. |
  93.         print
  94.                 'State    Read    Next    Write' print.
  95.         self binaryDo: [:x :y |
  96.             (x printString , '    ', y printString) print]
  97. ]
  98. Class Tape :Object
  99. | tape position |
  100. [
  101.         with: aString
  102.                 tape <- '#', aString, '#'.
  103.                 position <- tape size
  104. |
  105.         read
  106.                 ^ tape at: position
  107. |
  108.         write: aChar
  109.                 tape at: position put: aChar.
  110. |
  111.         left
  112.                 (position > 1)
  113.                         ifTrue: [position <- position - 1]
  114. |
  115.         right
  116.                 (position = tape size)
  117.                         ifTrue: [tape <- tape, '#'].
  118.                 position <- position + 1
  119. |
  120.         printString
  121.                 ^ (tape copyFrom: 1 to: position - 1), '{',
  122.                   ((tape at: position) asString), '}',
  123.                   (tape copyFrom: position + 1 to: tape size)
  124. ]
  125.